package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何实现链表的逆序
func main() {
	head := &common.LNode{}
	common.CreateNode1(head, 8)

	fmt.Println("逆序前：", head)

	//reverse(head)
	//recursiveReverse(head)
	insertReverse(head)

	fmt.Println("逆序后：", head)
}

// 方法一：就地逆序
func reverse(head *common.LNode) {

	// previous   current   Next
	//    a        b   ->   c   ->   d
	//
	//         previous   current   Next
	//    a   <-   b        c   ->   d

	if head == nil || head.Next == nil {
		return
	}

	var previous, next *common.LNode
	current := head.Next

	for current != nil {
		next = current.Next
		current.Next = previous
		previous = current
		current = next
	}

	head.Next = previous

}

func recursiveReverseChild(node *common.LNode) *common.LNode {
	if node == nil || node.Next == nil {
		return node
	}

	// 原链表的尾节点
	newHead := recursiveReverseChild(node.Next)

	// node = a    node.Next = b
	// a -> b => a <> b => a <- b
	node.Next.Next = node
	node.Next = nil

	return newHead
}

// 方法二：递归法
func recursiveReverse(head *common.LNode) {
	// 该数据结构中，链表的头节点不存储数据
	firstNode := head.Next
	newHead := recursiveReverseChild(firstNode)
	head.Next = newHead
}

// 方法三：插入法
func insertReverse(head *common.LNode) {
	if head == nil || head.Next == nil {
		return
	}

	var current, next *common.LNode
	current = head.Next.Next // 第 2 个数据节点
	head.Next.Next = nil     // 第 1 个数据节点将作为新链表的尾结点

	// a    b -> c
	// a <- b    c
	// b -> a    c

	for current != nil {
		next = current.Next
		current.Next = head.Next
		head.Next = current
		current = next
	}
}
